/*
 * Name:string algorithm
 * Description:
 * Date:2018/08/20
 * Author：JunQiu
 * */
#include <string>
#include <iostream>

using namespace std;

// 暴力搜索
// 时间复杂度：O(m * n)
int violent(string str, string searchStr) {
    int strLen = str.size();
    int searchStrLen = searchStr.size();
    int index;
    // 防止数组出界
    for (int i = 0; i < strLen - searchStrLen + 1; ++i) {
        index = i;
        for (int j = 0; j < searchStrLen; ++j) {
            if (searchStr[j] == str[index]) {
                if (j == searchStrLen - 1)
                    return index - searchStrLen + 2;
                index++;
            } else
                break;
        }
    }
    return -1;
}

// next数组虽然可以将最长相同前缀/后缀整体右移一位，next[0]=-1(表示第一位都匹配失败，继续往前匹配即可)，但是主要要理解如何用递归的方式得到
// 计算KMP的next数组,这里指匹配四失败时，子串需要移动的距离j-next[j],即i应该继续和next[j]匹配
// ????
void kmpNext(string searchStr, int next[]) {
    int searchLen = searchStr.size();
    next[0] = -1;
    int j = 0, k = -1;
    while (j < searchLen - 1) {
        if (k == -1 || searchStr[k] == searchStr[j])
            next[++j] = next[++k];
        else
            k = next[j];
    }
}

// kmp
// 时间复杂度：O(m * n)，即kmp算法过程的O(m)和next生成的O(n)
int kmp(string str, string searchStr) {
    int strLen = str.size();
    int searchStrLen = searchStr.size();
    int next[20] = {0};
    kmpNext(searchStr, next);
    int i = 0, j = 0;
    while (i < strLen && j < searchStrLen) {
        // 当j=-1 / str[i] == searchStr[j]，继续往前匹配
        // j=-1,表示上一次第一个字符都匹配失败，需要继续往前匹配
        if (j == -1 || str[i] == searchStr[j])
            i++, j++;
        else {
            // 子串需要移动的距离j-next[j],即i应该继续和next[j]匹配
            j = next[j];
        }
    }
    if (j == searchStrLen)
        return i - j + 1;
    else
        return -1;
}


// bad char
void bad(string searchStr, int bad[]) {
    int strLen = searchStr.size();
    // 存储所有字符的情况，当字符串越长，空间换时间效果越好
    for (int i = 0; i < 256; ++i) {
        // 初始化为searchStr长度
        bad[i] = strLen;
    }
    for (int j = 0; j < strLen; ++j) {
        // 修改在子串（模式串）中出现的字符(考虑最右端到坏字符的距离)
        bad[searchStr[j]] = strLen - 1 - i;
    }
}


// good
void good(string searchStr, int good[]) {

}


// BM
int bm(string str, string searchStr) {
}